package com.jack.leetcode.每日一题;

/*** 
 * @author zhangjie
 * @date 2020/4/15 20:30
 */
public class 零一矩阵 {

    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int dp[][] = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = matrix[i][j] == 0 ? 0 : 10000;
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(i-1>=0){
                    dp[i][j] = Math.min(dp[i-1][j]+1,dp[i][j]);
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(j-1>=0){
                    dp[i][j] = Math.min(dp[i][j-1]+1,dp[i][j]);
                }
            }
        }
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                if(i+1<m){
                    dp[i][j] = Math.min(dp[i+1][j]+1,dp[i][j]);
                }
            }
        }
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                if(j+1<n){
                    dp[i][j] = Math.min(dp[i][j+1]+1,dp[i][j]);
                }
            }
        }
        return dp;
    }
}
